package com.g02.by;

import com.g02.qt.ListNode;

import java.util.Stack;

public class NumAdd {
    static ListNode useStack(ListNode l1, ListNode l2) {
        // 使用栈来完成倒序访问
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        // 入栈
        for (ListNode t = l1; t != null; t = t.next) {
            s1.push(t);
        }
        for (ListNode t = l2; t != null; t = t.next) {
            s2.push(t);
        }
        // 开始相加
        ListNode cur = null;
        int addr = 0;
        while (!s1.isEmpty() && !s2.isEmpty()) {
            ListNode p1 = s1.pop();
            ListNode p2 = s2.pop();
            int n = p1.val + p2.val + addr;
            p1.val = n >= 10 ? n - 10 : n;
            addr = n >= 10 ? 1 : 0;
            p1.next = cur;
            cur = p1;
        }
        // 其中一个数已经加空了，如果还有未加完的数就继续加完
        Stack<ListNode> s = s1.isEmpty() ? s2 : s1;
        while (!s.isEmpty()) {
            ListNode p = s.pop();
            int n = p.val + addr;
            p.val = n >= 10 ? n - 10 : n;
            addr = n >= 10 ?  1 : 0;
            p.next = cur;
            cur = p;
        }
        // 如果上面同时为空后，还有进位，则把改进位加上
        if (addr != 0) {
            cur = new ListNode(addr, cur);
        }
        return cur;
    }
}
